package LeetCode.leetcode142;

import java.util.HashSet;

public class Main {
    /**
     * 第一次写的算法      超时了，估计是有问题
     * @param head
     * @return
     */
    public ListNode detectCycle1(ListNode head) {
        int slowSteps = 0;
        int fastSteps = 0;
        ListNode slow;
        ListNode fast;
        slow = head;
        fast = head;
        while (fast.next != null && fast.next.next != null && fast != slow) {
            fast = fast.next.next;
            fastSteps += 2;
            slow = slow.next;
            slowSteps += 1;
        }
        if (fast == slow) {
            int cycleSize = fastSteps - slowSteps;
            fast = head;
            int listSize = 1;
            while (fast.next != null) {
                fast = fast.next;
                listSize++;
            }
            slow = head;
            for (int i = 0; i < listSize - cycleSize - 1; i++) {
                slow = slow.next;
            }
            return slow;
        }else {
            return null;
        }
    }

    /**
     * 使用HashSet
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode node = head;
        while (node != null){
            if (set.contains(node)){
                return node;
            }else {
                set.add(node);
                node = node.next;
            }
        }
        return null;
    }

    /**
     * 使用双指针法
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}
